HW#2 --- last modified February 17 2019 19:23:10..

Solution set.

Due date: Mar 14

Files to be submitted:
  Hw2.zip

Purpose:

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO3 -- Describe a language in terms of a regular expression.

LO4 -- Find a regular expression for a language described by a finite automaton and conversely.

LO5 -- Construct a deterministic finite automaton from a non-deterministic one.

LO6 -- Minimize a deterministic automaton.

Specification: For this homework, you should do the following exercises, writing them up in a file Hw2.pdf or Hw2.html (your choice). When I say provide screen PNG screenshots, embed these into your Hw2.pdf or Hw2.php. Remember the maximum file upload size is 2MB so make sure to use compressed graphics.

1. Do research on the internet to try to find the applicable specification and come up with regular expressions (in the notation of our class) for the following: (a) either http or https schemed urls, (b) C language variable names, (c) Java integer literals, and (d) valid social security numbers.
2. Pick your favorite regular expression from amongst those of the last problem, use JFLAP to step through the process of converting this regular expression into an NFA. Provide PNG screenshots of going through this process and save your final NFA to a .jff file that you include with the homework. Take this resulting NFA and use JFLAP to see what happens when you try to convert it back into a regular expression (provide PNG screenshots). Along with your screenshots provide some commentary sufficient to prove that you understand what is happening as you are stepping through each process.
3. Use JFLAP to step through the process of converting the NFA of the previous problem into a DFA. Provide PNG screenshots of going through this process and save your final DFA to a .jff file that you include with the homework. Along with your screenshots provide some commentary sufficient to prove that you understand what is happening as you are stepping through each process. To make this step somewhat feasible... Look at the automata you got from the previous step, you will notice that you get many copies of states doing essentially the same stuff but maybe with a different alphabet symbol. Choose single representative states of each state that you got from the previous part, call that your starting machine and convert it to a DFA.
4. Use JFLAP to step through the process of minimizing the DFA of the previous problem into a minimal DFA. Provide PNG screenshots of going through this process and save your final DFA to a .jff file that you include with the homework. Along with your screenshots provide some commentary sufficient to prove that you understand what is happening as you are stepping through each process.
5. For this problem to receive credit your proof should use the style of argument asked for. Prove the regular languages are: (a) closed under intersection via a cartesian product argument, (b) closed under complement, (c) closed under difference, and (d) closed under reversal via induction on the complexity of the regular expressions (Here given `L` its reverse `L^R` is `{w^R | w \in L}`).

Point Breakdown